﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SAI
{
    class BFS
    {
        public static Metrics metrics = new Metrics();
        public static Node search(Node start, Node goal)
        {
            metrics.clearMetrics();
            DateTime dtStart = DateTime.Now;
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(start);
            start.visited();
            int x = 1;
            while (queue.Count > 0)
            {
                double total = metrics.Size * x;
                x++;
                total += queue.Count;
                metrics.Size = total / x;
                Node n = queue.Dequeue();
                metrics.NodesGenerated += n.getOutNeighbors().Count;
                if (n == goal)
                {
                    metrics.Time = (DateTime.Now - dtStart).TotalSeconds;
                    return n;
                }
                metrics.NodesExpanded++;
                
                foreach (Node outNode in n.getOutNeighbors())
                {
                    if (!outNode.Visited)
                    {
                        queue.Enqueue(outNode);
                        outNode.visited();
                        outNode.Parent = n;
                    }
                }
            }
            return null;
        }
    }
}
